package baseclass.z_lruCache;

import java.util.HashMap;
import java.util.Map;

/**
 * 自己设置一个LRUCache。
 * 采用Map<K,node<K,V>>,node采用双向链表
 *
 * 本身底层还是一个双向链表存储，链表定位慢，那就解决这个问题。
 * 所以采用Hash进行定位。链表是一个K，V的结构，hash通过关联K直接定位到对应链表，
 * 这样CRUD性能都是O(1)
 * @date 2020/3/5 18:40
 */
public class Code03_DIY_LRUCache<K, V> {
    static class Node<K, V> {
        K k;
        V v;
        Node next, pre;

        public Node(K k, V v) {
            this.k = k;
            this.v = v;
        }
    }

    private Map<K, Node<K, V>> cache;
    private Node first;
    private Node last;
    private final int CAPACITY;
    public Code03_DIY_LRUCache(int capacity) {
        CAPACITY = capacity;
        this.cache = new HashMap<>();
    }

    public void put(K k, V v) {
        assertNotPointKey(k);
        Node<K, V> node = cache.get(k);
        //1判断是否包含K，若包含则删除
        if (node != null) {
            removeFromCacheAndList(node);
        }
        //2若不包含，判断size是否已满,满则移除最后一个
        if (cache.size() >= CAPACITY) {
            removeFromCacheAndList(last);
        }
        //3在链表头部插入node，并放入到map
        addToCacheAndFirstList(k, v);

    }

    public V get(K k) {
        assertNotPointKey(k);
        Node<K, V> node = cache.get(k);
        if (node == null) return null;
        //否则移除node，
        removeFromCacheAndList(node);
        //然后添加到最前面
        addToCacheAndFirstList(k, node.v);
        return node.v;
    }

    public V remove(K k) {
        assertNotPointKey(k);
        Node<K, V> node = cache.get(k);
        if (node == null) return null;
        //移除node
        removeFromCacheAndList(node);
        return node.v;
    }

    private void addToCacheAndFirstList(K k, V v) {
        Node<K, V> node = new Node<>(k, v);
        cache.put(k, node);
        addFirstNodeToList(node);
    }

    private void assertNotPointKey(K k) {
        if (k == null) throw new NullPointerException();
    }

    private void removeFromCacheAndList(Node<K, V> node) {
        if(cache.remove(node.k) != null){
            removeListNode(node);
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node p = first;
        while (p != null) {
            sb.append(p.k).append(" : ").append(p.v).append("\r\n");
            p = p.next;
        }
        return sb.toString();
    }

    private void addFirstNodeToList(Node<K, V> node) {
        if (first == null) {
            first = last = node;
            return;
        }
        node.next = first;
        first.pre = node;
        first = node;
    }

    private void removeListNode(Node<K, V> node) {
        if (first == null) throw new NullPointerException("the inner list is null");
        //first = last = node
        if (first == last) {
            if (first != node) throw new RuntimeException("error");
            first = last = null;
            return;
        }
        //assert list.size >=2
        if (node == first) {
            Node next = first.next;
            first.next = null;
            next.pre = null;
            first = next;
        } else if (node == last) {
            Node pre = last.pre;
            pre.next = null;
            last.pre = null;
            last = pre;
        } else {
            Node pre = node.pre;
            Node next = node.next;
            pre.next = next;
            next.pre = pre;
            node.pre = node.next = null;
        }
    }

    public int size() {
        return cache.size();
    }

    public static void main(String[] args) {
        Code03_DIY_LRUCache<Integer, Integer> cache = new Code03_DIY_LRUCache<>(5);
        System.out.println("放入0");
        cache.put(0, 0);
        System.out.println(cache);
        System.out.println("放入0");
        cache.put(0, 0);
        System.out.println(cache);
        for (int i = 1; i <= 5; i++) {
            cache.put(i, i);
            System.out.println(cache);
        }
        System.out.println("放入6");
        cache.put(6, 6);
        System.out.println(cache);
        System.out.println("放入7");
        cache.put(7, 7);
        System.out.println(cache);
        System.out.println("放入5");
        cache.put(5, 5);
        System.out.println(cache);

        System.out.println("============查询5");
        cache.get(5);
        System.out.println(cache);
        System.out.println("============查询6");
        cache.get(6);
        System.out.println(cache);
        System.out.println("============查询3");
        cache.get(3);
        System.out.println(cache);

        System.out.println("删除3");
        cache.remove(3);
        System.out.println(cache);
        System.out.println("删除5");
        cache.remove(5);
        System.out.println(cache);

    }
}
